
const arr =[1,8,5,3,4,9,7,6,0]

function getSequence2(arr) {
    const len = arr.length;
    const result = [0]; 
    const p = arr.slice();
    let resultLastIndex;
    let start;
    let end;
    let middle = 0;
    for (let i = 0; i < len; i++) {
        const arrI = arr[i]; 
        if (arrI !== 0) {
            resultLastIndex = result[result.length - 1];
            if (arr[resultLastIndex] < arrI) {
                p[i] = resultLastIndex // 记录上一次
                result.push(i);
                continue
            }
            start = 0;
            end = result.length - 1; 
            while (start < end) {
                middle = ((start + end) / 2) | 0;
                if (arr[result[middle]] < arrI) { 
                    start = middle + 1;
                } else {
                    end = middle;
                }
            }
            if (arrI < arr[result[start]]) {
                if (start > 0) {
                    p[i] = result[start - 1]; // 记录上一次
                }
                result[start] = i;
            }
        }
        let len = result.length
        let last = result[len - 1]
        while (start-- > 0) { // 倒序追溯
            result[start] = last
            last = p[last]
        }
    }
    return result
}

// getSequence(arr)
console.log(getSequence2(arr))